User blog:B1mb0w/Deeply Nested Ackermann
Deeply Nested Ackermann The Deeply Nested Ackermann function (signified with a lowercase d) is defined by generalizing the Modified Ackermann Function MA() with a variable input parameter array: \(d(x_1,x_2,x_3,x_4, ... ,x_n)\) Rules for the d function are similar to MA function rules but generalised as follows: \(d() = 0\) This is a null function that always returns zero. \(d(m) = m+1\) This is equivalent to MA(0,m) The next example is equivalent to the \(MA(m,n)\) function. \(d(m,n) = MA(m,n)\) And the same rules apply: \(d(m,n)\) defined as: ◾ \(n+1\) if m=0 , ◾ \(d(m−1,d(m-1,m))\) if n=0 , or ◾ \(d(m−1, d(m,n−1))\) otherwise. For 3 parameters, the rules are generalised and extended as follows: \(d(m_1,m_2,m_3)\) defined as: ◾ \(d(m_{2},m_{3})\) if \(m_1=0\) , ◾ \(d(m_1−1, d(m_1,m_2-1), d(m_1,m_2,m_3-1))\) if \(m_1>0\) , \(m_2>0\) and \(m_3>0\) ◾''but'' \(d(m_1,m_2-1)\) is substituted by \(d(m_1-1,m_1)\) if \(m_2=0\) ◾''and'' \(d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1,m_2-1,m_2)\) if \(m_3=0\) ◾''or'' \(d(m_1,m_2,m_3-1)\) is substituted by \(d(m_1-1,m_1,m_1)\) if \(m_2=0\) and \(m_3=0\) General Example Instead of giving an example for \(d(x_{1},x_{2},x_{3},x_{4})\) next, it is actually easier to follow the general example for: \(d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n})\) defined as this deeply nested function: \(d(x_{1}-1, d(x_{1},x_{2}-1), d(x_{1},x_{2},x_{3}-1), d(x_{1},x_{2},x_{3},x_{4}-1), ..., d(x_{1},x_{2},x_{3},x_{4}, ... ,x_{n}-1)\) The only substitution rules that need to be followed are: Leading Zeros rule L1. \(d(0,0, ...,0,x,y,z)\) is substituted for \(d(x,y,z)\) in all cases Trailing Zeros rule T1. \(d(x,y,z,0,0, ... ,-1)\) is substituted for \(d(x,y,z-1,z,z, ... ,z)\) in all cases Calculated Examples \(d() = 0\) This is a null function that always returns zero. \(d(3) = 4\) This is the successor function \(d(1,2) = 5\) This is equal to MA(1,2) = 2+3 \(d(1,n) >> f_0(n+2)\) Using the Comparison Rule C1 (at the end of this blog post) we get: \(d(m,n) >> f_{m-1}(n)\) \(d(1,0,0)\) is the first non trivial calculation and expands as follows: \(= d(0,d(0,1),d(0,1,1))\) then apply the Leading Zeros rule \(= d(d(1),d(1,1)) = d(2,4) = 20\) This is equal to MA(2,4) = 3.4+8 then \(d(1,0,1) = d(0,d(0,1),d(1,0,0)) = d(d(1),d(1,0,0)) = d(2,20) = 68\) This is equal to MA(2,20) = 3*20+8 and \(d(1,0,2) = d(2,d(1,0,1)) = d(2,68)\) next \(d(1,1,0) = d(0,d(1,0),d(1,0,1)) = d(3,68) >> f_2(68)\) \(d(1,1,1) = d(0,d(1,0),d(1,1,0)) = d(3,d(3,68)) >> f_2^2(68)\) \(d(1,1,n) >> f_2^{n+1}(68)\) \(d(1,2,0) = d(0,d(1,1),d(1,1,2)) >> d(4,f_2^3(68)) >> f_3(f_2^3(68))\) \(d(1,2,n) >> f_3^{n+1}(f_2^3(68))\) \(d(1,3,0) = d(0,d(1,2),d(1,2,3)) >> d(5,f_3^4(f_2^3(68))) >> f_4(f_3^4(f_2^3(68)))\) \(d(1,3,n) >> f_4^{n+1}(f_3^4(f_2^3(68)))\) or \(d(1,3,n+p) >> f_4^{n+1}(n) >> f_5(n)\) where \(p << n\) and \(d(1,m,n+p) >> f_{m+1}^{n+1}(n) >> f_{m+2}(n)\) where \(p << n\) Some Comparisons \(d(3,0) = 59\) \(d(3,9) >> d(2,16) >> 1,000,000\) \(d(3,206) >> d(2,324) >>\) Googol \(d(4,0) = d(3,5099) >> 3^{5099}\) \(d(1,1,0) = d(3,68) <<\) Googol \(d(1,1,1) = d(d(1,0),d(1,1,0)) = d(3,d(3,68)) >> 3^{3^{68}} <<\) Googolplex \(d(1,1,2) = d(d(1,0),d(1,1,1)) = d(3,d(1,1,1)) >> d(3,3^{3^{68}}) >>\) Googolplex \(d(1,3,0) >> d(6,1) >> g_1\) where \(g_{64} = G\) Graham's number \(d(1,4,0) = d(6,d(1,3,4)) >> d(6,g_1)\) \(d(1,4,1) = d(6,d(1,4,0))\) Comparing d functions with 3 and 2 input parameters we get: \(d(1,y,z) = d(y+2,d(1,y,z-1))\) Then \(d(2,0,0) = d(1,d(1,2),d(1,2,2)) >> d(1,5,f_4(2)) >> f_7(f_4(2))\) \(d(2,0,1) = d(1,d(1,2),d(2,0,0)) >> d(1,5,f_7(f_4(2))) >> f_7^2(f_4(2))\) \(d(2,0,n) >> f_7^{n+1}(f_4(2))\) Graham's Number The d function can reach \(g_1\), where \(g_{64} = G\) (Graham's number), relatively quickly. As shown above \(d(1,3,0) >> g_1\) . \(g_0 = 4\) and \(g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3 << f_5(3) = f_{g_0}(3)\) \(g_2 << f_{g_1}(3)\) and likewise till \(G = g_{64} << f_{g_{63}}(3)\) In the fast-growing hierarchy, Graham's Number can be shown to be less than \(f_{\omega+1}(64) = f_{\omega}^{64}(64)\). \(G\) is closer to, but still less than \(f_{\omega}^{64}(5)\) . We need d functions with many more input parameters to reach G (Graham's Number). \(d(6,1) >> f_5(3) >> g_1\) \(d( d(6,1), 1) >> g_2\) \(d(6,1,1)\) we will get \(d(6,1)\) nested in its long expansion and therefore \(d(6,1,1) >> g_2\) by a very great amount. We can reach \(g_3\) by moving to 4 input parameters \(d(6,1,1,1) >> g_3\) We finally reach G (Graham's Number) with 64 input parameters \(d(6,1,1,1, ..., 1,1) >> G\) Growth Rate Using the comparison rule C1 at the end of this blog: \(d(m,n) >> f_{m-1}(n+2)\) we can see the growth rate for: \(d(n+1,n-2) >> f_n(n)\) or \(f_{\omega}(n)\) The growth rate for \(d(x_1,x_2,x_3,x_4,...,x_n)\) is comparable to \(f_{\omega+1}(n)\) 'Next Blog' To get more impressive growth growths, we can create a strong version of this function. My next blog post introduces the Strong D Function based on the above (weak) d function. 'Comparison Rule' A simple way to compare the d function to the Fast-growing hierarchy, is: Comparison Rule C1. \(d(m,n-2+\delta) >> f_{m-1}(n)\) where \(\delta << n\) or \(d(m,n) >> f_{m-1}(n)\) To illustrate this rule we start with: \(d(0,n) = f_0(n)\) by definition \(d(1,0) = d(0,d(0,1)) = f_0(f_0(1)) = f_0^2(1)\) \(d(1,1) = d(0,d(1,0)) = f_0(f_0^2(1)) = f_0^3(1)\) \(d(1,2) = d(0,d(1,1)) = f_0^4(1)\) and \(d(1,n) = d(0,d(1,n-1)) = f_0^{n+2}(1) = f_0^3(n)\) by definition then \(d(2,0) = d(1,d(1,2)) = f_0^3(f_0^3(2)) = f_0^3(f_0(4)) = f_0^4(4) = f_1(4)\) \(d(2,1) = d(1,d(2,0)) = f_0^3(f_1(4)) = f_0(f_0^2(f_1(4))) = f_0(f_1(5))\) by definition \(d(2,2) = d(1,d(2,1)) = f_0^3(f_0(f_1(5))) = f_0^2(f_0^2(f_1(5))) = f_0^2(f_1(6)) = f_1(7)\) by definition and \(d(2,n) = f_0^{n/2}(f_1(n+4)) >> f_1(n.3/2+4) >> f_1(n+4)\) then \(d(2,d(2,n)) >> f_1(f_1(n+4)+4) >> f_1(f_1(n+4)) = f_1^2(n+4)\) \(d(3,0) = d(2,d(2,3)) >> f_1^2(7)\) \(d(3,1) = d(2,d(3,0)) >> f_1^3(7) >> f_2(3)\) \(d(3,2) >> f_1^4(3) = f_1^3(n)\) where \(n <= f_1(7)\) \(d(3,m) >> f_1^{m+2-p}(n)\) where \(n <= f_1^p(7)\) \(d(3,n-2+p) >> f_1^{n}(n) >> f_2(n)\) where \(n <= f_1^p(7)\) then \(d(m,n-2+\delta) >> f_{m-1}(n)\) where \(\delta << n\) 'Alternative Comparison Rule' The growth rate of the d function is comparable to the Fast-growing hierarchy , with this rule: A1. \(d(x,y) = d(x-1, d(x,y-1)) = d^{y+2}(x-1,x)\) \(f_x(y) = f_{x-1}^{y}(y)\) \(f_x(y)\) is greater than \(d(x,y)\) because \(f_2(y) = 2.2^y\) and \(d(2,y) = 3.y + 8\) and both growth functions recursively grow at the same rate for greater values of x. So we can use this Comparison Rule: C1. \(f_x(y+2) << d(x+1,y)\) because \(f_{x-1}^{y+2}(y+2) << d^{y+2}(x,x+1)\) and every \(d(x,n) >> f_{x-1}(n)\) by at least a factor of 3 to 2 for any n. This is not obvious because comparing the last nested function we get \(f_{x-1}(y+2) << d(x,x+1)\) in the case y>x+1, the f function dominates and the d(x,) function growth rate may not be fast enough to compensate, especially when y >> x. Proof Let \(f_{x-1}^r(y) >> d^r(x,x+1)\) be any case where the f function is dominating the d function. When this is true then because the d(x,) function growth rate dominates, then it must be true that \(f_{x-1}(y) >> d(x,x+1)\) and: \(f_{x-1}(y) = d(x,x+1) + a_0\) \(d(x,n) >> f_{x-1}(n)\) by a minimum of a factor of 3 to 2, so if \(f_{x-1}^2(y) >> d^2(x,x+1)\) then \(a_0\) must have a minimum size. \(2.f_{x-1}(y) = 2.(d(x,x+1) + a_0) >> 3.d(x,x+1)\) so \(a_0 >> 3.d(x,x+1)/2\) lets assume \(a_0 = 3.d(x,x+1)/2 + a_1\) At this point we have prooved that if r>=2 then y will be >=r. Lets calculate some trivial examples: \(f_0(y) = d(1,2) + a_0 = d(1,2) + 3.d(1,2)/2 + a_1 >> 5.d(1,2)/2 = 5*5/2 = 12.5\) so \(y >> 11\) \(f_1(y) = d(2,3) + a_0 = d(2,3) + 3.d(2,3)/2 + a_1 >> 5.d(2,3)/2 = 5*17/2 = 42.5\) so \(y >> 3\) and in all other cases y>x+1 from the comparison rule, so y>3. But how big must \(a_1\) be for r=3 such as \(f_{x-1}^3(y) >> d^3(x,x+1)\). \(2.2.f_{x-1}(y) = 4.(d(x,x+1) + a_0) = 4.(d(x,x+1) + 3.d(x,x+1)/2 + a_1) = 7.d(x,x+1) + 4.a_1) >> 3.3.d(x,x+1)\) and \(7.d(x,x+1) + 4.a_1) >> 9.d(x,x+1)\) so \(a_1 >> d(x,x+1)/2\) lets assume \(a_1 = d(x,x+1)/2 + a_2\) and \(a_0 = 2.d(x,x+1) + a_2)\) and lets calculate: \(f_2(y) = d(3,4) + a_0 = d(3,4) + 2.d(3,4) + a_2 >> 3.d(3,4) = 3*5099 = 15297\) so \(y >> 10\) and in all other cases y>x+1 from the comparison rule, so y>6. Completion of Proof This proof by induction shows that each iteration of calculating \(a_n\) for r>=4 will require the minimum bound for y to increase by >=1 every time. Which means the requirement that y>=r must change to y>r and: \(f_x(y+2) << d(x+1,y)\) for all cases including any examples of \(f_{x-1}^r(y) >> d^r(x,x+1)\) Category:Blog posts